package array;

/**
 * @Author quan
 * @Description 有序数组的平方
 * @Date 2023/4/25 17:20
 */
public class Demo3_sortedSquares {
    /**
     * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
     * 输入：nums = [-4,-1,0,3,10]     * 输出：[0,1,9,16,100]
     * 解释：平方后，数组变为 [16,1,0,9,100]
     * 排序后，数组变为 [0,1,9,16,100]
     * @param nums
     * @return
     */
    // 方法1：创建新数组
//    public int[] sortedSquares(int[] nums) {
//        //思路：创建一个新数组存储平方后的元素值，然后再排序
//        int[] newArr = new int[nums.length];
//        //遍历旧数组，获取新数组的元素值
//        for (int i = 0; i < nums.length; i++) {
//            newArr[i] = nums[i] * nums[i];
//        }
//        //对新数组进行排序
//        Arrays.sort(newArr);
//        return newArr;
//    }

    //原地获取结果，不允许创建新的数组
//    public int[] sortedSquares(int[] nums) {
//        for (int i = 0; i < nums.length; i++) {
//            nums[i] = nums[i]*nums[i];
//        }
//        Arrays.sort(nums);
//        return nums;
//    }

    //方法2：双指针法:关键在于该题是有序的数组，因此最大值一定在两端，所以将两端的数据进行比较获取最大值写入新数组的末端
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int k = nums.length-1;
        for (int i = 0, j = nums.length-1; i <= j;) {
            if(nums[i]*nums[i] <= nums[j]*nums[j]){
                result[k] = nums[j]*nums[j];
                k--;
                j--;
            }else{
                result[k] = nums[i]*nums[i];
                k--;
                i++;
            }
        }
        return result;
    }
}
